package leetcode_200;

import java.util.ArrayList;
import java.util.List;



/**
 *@author 周杨
 *BinaryTreeZigzagLevelOrderTraversal_103 ZIG形式遍历一个二叉树  每层改变遍历方向
 *describe:用尾递归的思想 AC 100%
 *2018年5月20日 下午3:30:10
 */
public class BinaryTreeZigzagLevelOrderTraversal_103 {
	List<List<Integer>> res;
	List<TreeNode> run;
	static class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		this.res=new ArrayList<List<Integer>>();
		if(root==null)
			return this.res;
		this.run=new ArrayList<TreeNode>();
		boolean flag=true;//确定遍历方向 true从左往右添加
		run.add(root);
		int start=0;
		while(start!=run.size()) {
			List<Integer> list=new ArrayList<Integer>();
			int end=run.size();
			if(flag)
				help1(list,start,end);
			else 
				help2(list,start,end);
			start=end;
			this.res.add(list);
			flag=!flag;
		}
		return this.res;
	}
	
	public void help1(List<Integer> list,int start,int end) {//顺序添加
		while(start<end) {
				TreeNode now=run.get(start);
				if(now.left!=null)
					run.add(now.left);
				if(now.right!=null)
					run.add(now.right);
				list.add(now.val);
				++start;
		}		
	}
	
	public void help2(List<Integer> list,int start,int end) {//尾递归
				TreeNode now=run.get(start);
				if(now.left!=null)
					run.add(now.left);
				if(now.right!=null)
					run.add(now.right);
				if(start+1!=end)
					help2(list,start+1,end);
				list.add(now.val);
	}		
	
}
